// 双向链表的封装
class DoublyLinkedList {
  head = null;
  tail = null;
  length = 0;

  append(element) {
    // 1.创建一个节点类
    const newNode = new Node(element);
    // let currentNode = this.head;
    // 2.通过链表长度判断是不是第一个节点
    if (!this.length) {
      // 第一次append
      this.head = newNode;
      // this.tail = newNode;
    } else {
      // 第 n+1 次append: 找到最后一个节点
      // while (currentNode.next) currentNode = currentNode.next;
      // currentNode.next = newNode;
      // newNode.prev = currentNode;
      // 简单做法:
      newNode.prev = this.tail;
      this.tail.next = newNode;
    }
    this.tail = newNode;
    // 3.长度+1
    this.length++;
  }

  insert(position, element) {
    // 1.下标越界处理
    if (position < 0 || position > this.length) return false;
    const newNode = new Node(element);
    // 2.判断是否为第一次插入
    if (!this.length) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      if (position === 0) { // 2.1 判断是否为第一个节点插入
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
      } else if (position == this.length) { // 2.2 判断是否为最后一个节点插入
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
      } else { // 2.3 判断其它情况
        // 2.3.1 找到目标元素
        let index = 0;
        let currentNode = this.head;
        while (index++ < position) {
          currentNode = currentNode.next;
        }
        newNode.prev = currentNode.prev;
        newNode.next = currentNode;
        currentNode.prev.next = newNode;
        currentNode.prev = newNode;
      }
    }
    // 3.长度+1
    this.length++;
  }

  get(position) {
    const _size = this.length;
    let currentNode = null;
    // 1.下标越界处理
    if (position < 0 || position >= _size) return null;
    if (position == 0) { // 2.返回第一个
      return this.head.element;
    } else if (position == _size - 1) { // 3.返回最后一个
      return this.tail.element;
    } else { // 4.其它情况
      // 折半查找 _size >> 1 等于 Math.floor(_size/2) 但是效率高
      const halfNum = _size >> 1;
      if (halfNum >= position) {
        // console.log("从头开始");
        // 当前位置信息小于或等于一半 从头开始找
        let index = 0;
        currentNode = this.head;
        // 找目标元素
        while (index++ < position) currentNode = currentNode.next;
      } else {
        // console.log("从尾开始");
        // 当前位置信息大于一半 从尾开始找
        let index = _size - 1;
        currentNode = this.tail;
        while (index-- > position) currentNode = currentNode.prev;
      }
    }
    return currentNode.element;
  }

  indexOf(element) {
    let currentNode = this.head;
    let index = 0;
    while (currentNode) {
      if (currentNode.element === element) return index;
      currentNode = currentNode.next;
      index += 1;
    }
    return -1;
  }

  update(position, element) {
    // 1.下标越界处理
    if (position < 0 || position >= this.length) return false;
    // 2.找到目标节点 修改element属性
    let currentNode = this.head;
    let index = 0;
    if (position === 0) { // 头
      this.head.element = element;
    } else if (position === this.length - 1) { // 尾
      this.tail.element = element;
    } else { // 其它
      while (index++ < position) currentNode = currentNode.next;
      currentNode.element = element;
    }
    return true;
  }

  removeAt(position) {
    // 1.下标越界判断
    if (position < 0 || position >= this.length) return null;
    let element = "";
    if (this.length == 1) {
      // 只有一个节点
      this.head = null;
      this.tail = null;
    } else if (position === 0) {
      element = this.head.element;
      this.head.next.prev = null;
      // 第一个节点指向
      this.head = this.head.next;
    } else if (position === this.length - 1) {
      element = this.tail.element;
      this.tail.prev.next = null;
      // 最后一个节点指向
      this.tail = this.tail.prev;
    } else {
      let index = 0;
      let currentNode = this.head;
      while (index++ < position) currentNode = currentNode.next;
      currentNode.prev.next = currentNode.next;
      currentNode.next.prev = currentNode.prev;
      element = currentNode.element;
    }
    // 长度-1
    this.length -= 1;
    return element;
  }

  remove(element) {
    // 1.获取element的下标
    return this.removeAt(this.indexOf(element));
  }

  isEmpty() {
    return !this.length;
  }

  size() {
    return this.length;
  }

  // 获取链表第一个节点
  getHead() {
    return this.head;
  }

  // 获取链表最后一个节点
  getTail() {
    return this.tail;
  }

  // 默认向后遍历
  toString() {
    return this.backwardString();
  }

  // 向前遍历
  forwardString() {
    let currentNode = this.tail;
    let resultList = [];
    while (currentNode) {
      resultList.push(currentNode.element);
      currentNode = currentNode.prev;
    }
    return resultList.join(",");
  }

  // 向后遍历
  backwardString() {
    let currentNode = this.head;
    let returnList = [];
    while (currentNode) {
      returnList.push(currentNode.element);
      currentNode = currentNode.next;
    }
    return returnList.join(",");
  }
}

// 节点类
class Node {
  constructor(element) {
    this.element = element;
    this.prev = null;
    this.next = null;
  }
}

const doublyLinked = new DoublyLinkedList();

doublyLinked.append(1);
doublyLinked.append(2);
doublyLinked.append(3);
doublyLinked.append(4);
doublyLinked.append(5);

// TODO: 测试
// doublyLinked.insert(0, 100);
// doublyLinked.insert(4, 120);
// doublyLinked.insert(4, 110);
// doublyLinked.insert(1, 100);

console.log(doublyLinked);
console.log(doublyLinked.toString());
console.log(doublyLinked.forwardString());

console.log("第一个", doublyLinked.get(0));
console.log("倒数第二个", doublyLinked.get(doublyLinked.length - 2));
console.log("最后一个", doublyLinked.get(doublyLinked.length - 1));

// console.log(doublyLinked.indexOf(11));
// console.log(doublyLinked.indexOf(100));
// console.log(doublyLinked.indexOf(120));

// console.log(doublyLinked.update(0, "修改了第1个节点"));
// console.log(doublyLinked.update(3, "修改了第4个节点"));
// console.log(doublyLinked.update(doublyLinked.length - 1, "修改了最后一个节点"));

console.log(doublyLinked.toString());

console.log("\n");
console.log(doublyLinked.removeAt(0));
console.log(doublyLinked.toString());
// console.log(doublyLinked);

console.log("\n");
console.log(doublyLinked.removeAt(1));
console.log(doublyLinked.toString());

console.log("\n");
console.log(doublyLinked.removeAt(doublyLinked.length - 1));
console.log(doublyLinked.toString());

console.log("\n");
console.log(doublyLinked.remove(4));
console.log(doublyLinked.toString());

console.log("\n");
console.log(doublyLinked.size());
console.log(doublyLinked.isEmpty());
console.log(doublyLinked.getHead());
console.log(doublyLinked.getTail());
